package Top200;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2022-02-26 14:35
 * 计算出矩阵的每个元素的左边连续 1的数量，使用二维数组 left 记录，其中 left[i][j] 为矩阵第 i 行第 j 列元素的左边连续 1 的数量。
 * 然后对每一列调用84题的单调栈算法。
 */
public class maximalRectangle85 {
    public int largestRectangleArea(int[] heights) {
        int n= heights.length;
        int[] left=new int[n],right=new int[n];
        Stack<Integer> stack=new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                stack.pop();
            }
            left[i]=stack.isEmpty()?-1:stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n-1; i >= 0; i--) {
            while (!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            right[i]=stack.isEmpty()?n:stack.peek();
            stack.push(i);
        }
        int res=0;
        for (int i = 0; i < n; i++) {
            res=Math.max(res,(right[i]-left[i]-1)*heights[i]);
        }
        return res;
    }
    public int maximalRectangle(char[][] matrix) {
        int m=matrix.length,n=matrix[0].length;
        int[][] left=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j]=='1'){
                    left[i][j]=(j==0?0:left[i][j-1])+1;
                }
            }
        }
        int res=0;
        for (int j = 0; j < n; j++) {
            int[] heights=new int[m];
            for (int i = 0; i < m; i++) {
                heights[i]=left[i][j];
            }
            res=Math.max(res,largestRectangleArea(heights));
        }
        return res;
    }
}
